package jf.collections.primitive;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Map;

import static jf.collections.CollectionF.asSet;
import static jf.collections.CollectionF.asList;
import static jf.collections.CollectionF.asMap;
import jf.collections.ListX;
import static jf.collections.Tuple.asT;

/**
 * @author ivanalx
 * @date 29.05.2009 19:01:22
 */
public class LinkedHashSet<A> implements Set<A> {
	private Map<A, Entity<A>> mapContainer;

	private Entity<A> head;
	private Entity<A> tail;

	public LinkedHashSet() {
		mapContainer = new HashMap<A, Entity<A>>();
		head = null;
		tail = null;
	}

	public LinkedHashSet(Collection<? extends A> c) {
		ListX<A> as = asList(c).safe();
		mapContainer = new HashMap<A, Entity<A>>(as.size());
		Entity<A> last = tail;
		for (A a : as) {
			if (head == null) {
				head = new Entity<A>(a);
				last = head;
			} else {
				last.right = new Entity<A>(a);
				last.right.left = last;
				last = last.right;
			}
			mapContainer.put(a, last);
		}
		tail = last;
	}

	public LinkedHashSet(int initialCapacity, float loadFactor) {
		mapContainer = new HashMap<A, Entity<A>>(initialCapacity, loadFactor);
	}

	public LinkedHashSet(int initialCapacity) {
		mapContainer = new HashMap<A, Entity<A>>(initialCapacity);
	}

	@Override
	public int size() {
		return mapContainer.size();
	}

	@Override
	public boolean isEmpty() {
		return mapContainer.isEmpty();
	}

	@Override
	public boolean contains(Object o) {
		return mapContainer.containsKey(o);
	}

	@Override
	public Iterator<A> iterator() {
		return new FromLeftToRightIterator<A>(head, this);
	}

	public Iterator<A> rightIterator() {
		return new FromRightToLeftIterator<A>(tail, this);
	}

	@Override
	public Object[] toArray() {
		return mapContainer.keySet().toArray();
	}

	@Override
	public <T> T[] toArray(T[] a) {
		return mapContainer.keySet().toArray(a);
	}

	@Override
	public boolean add(A a) {
		if (mapContainer.keySet().contains(a)) return false;
		Entity<A> aEntity = new Entity<A>(a);
		mapContainer.put(a, aEntity);
		if (head != null) {
			aEntity.right = head;
			tail.left = aEntity;
			head = aEntity;
		} else {
			tail = aEntity;
			head = aEntity;
		}
		return true;
	}

	@Override
	public boolean remove(Object o) {
		Entity<A> aEntity = mapContainer.remove(o);
		if (aEntity == null) return false;
		if (head == tail && head == aEntity) {
			head = null;
			tail = null;
		} else if (head == aEntity) {
			head = aEntity.right;
		} else if (tail == aEntity) {
			tail = aEntity.left;
		} else {
			aEntity.left.right = aEntity.right;
			aEntity.right.left = aEntity.left;
		}
		return true;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		return mapContainer.keySet().containsAll(c);
	}

	@Override
	public boolean addAll(Collection<? extends A> c) {
		boolean isAddSomething = false;
		for (A a : c) {
			isAddSomething = add(a) || isAddSomething;
		}
		return isAddSomething;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		Set<?> set = asSet(c);
		boolean isSomethingRemoved = false;
		Iterator<A> iterator = this.iterator();
		while (iterator.hasNext()) {
			A nextElement = iterator.next();
			if (!set.contains(nextElement)) {
				iterator.remove();
				isSomethingRemoved = true;
			}
		}
		return isSomethingRemoved;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		Set<?> set = asSet(c);
		boolean isSomethingRemoved = false;
		Iterator<A> iterator = this.iterator();
		while (iterator.hasNext()) {
			A nextElement = iterator.next();
			if (set.contains(nextElement)) {
				iterator.remove();
				isSomethingRemoved = true;
			}
		}
		return isSomethingRemoved;
	}

	@Override
	public void clear() {
		tail = null;
		head = null;
		mapContainer.clear();
	}


	private Entity<A> removeElement(Entity<A> entity) {
		if (tail == entity && tail == head) {
			tail = null;
			head = null;
			return entity;
		} else if (tail == entity) {
			tail = entity.left;
			entity.left.right = null;
		} else if (head == entity) {
			head = entity.right;
			entity.right.left = null;
		} else {
			entity.left.right = entity.right;
			entity.right.left = entity.left;
		}
		mapContainer.remove(entity.a);
		return entity;
	}

	private class FromLeftToRightIterator<A> extends LeftRightIterator<A> {
		private FromLeftToRightIterator(Entity<A> pos, LinkedHashSet<A> as) {
			super(pos, as);
		}

		@Override
		public Entity<A> getNextIfPossible() {
			return getPos() != null? getPos().right: null;
		}
	}

	private class FromRightToLeftIterator<A> extends LeftRightIterator<A> {
		private FromRightToLeftIterator(Entity<A> pos, LinkedHashSet<A> as) {
			super(pos, as);
		}

		@Override
		public Entity<A> getNextIfPossible() {
			return getPos() != null? getPos().left: null;
		}
	}

	private abstract static class LeftRightIterator<A> implements Iterator<A>{
		private Entity<A> pos;
		private Entity<A> nextPos;
		private LinkedHashSet<A> set;


		private LeftRightIterator(Entity<A> pos, LinkedHashSet<A> set) {
			this.pos = null;
			this.nextPos = pos;
			this.set = set;
		}

		@Override
		public boolean hasNext() {
			return nextPos != null;
		}

		public Entity<A> getPos() {
			return nextPos;
		}

		public abstract Entity<A> getNextIfPossible();

		@Override
		public A next() {
			if (nextPos == null) throw new NoSuchElementException();
			pos = nextPos;
			nextPos = getNextIfPossible();
			return pos.a;
		}

		@Override
		public void remove() {
			if (pos == null) throw new NoSuchElementException();
			set.removeElement(pos);
		}
	}

	private static class Entity<A> {
		private Entity(A a) {
			this.a = a;
		}

		public A a;
		public Entity<A> left;
		public Entity<A> right;

		@Override
		public boolean equals(Object o) {
			if (this == o) {
				return true;
			}
			if (!(o instanceof Entity)) {
				return false;
			}

			Entity entity = (Entity) o;

			if (a != null ? !a.equals(entity.a) : entity.a != null) {
				return false;
			}

			return true;
		}

		@Override
		public int hashCode() {
			return a != null ? a.hashCode() : 0;
		}
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) {
			return true;
		}
		if (!(o instanceof Set)) {
			return false;
		}

		Set that = (LinkedHashSet) o;

		return !((mapContainer.size() != that.size()) || !mapContainer.keySet().containsAll(that));
	}

	@Override
	public int hashCode() {
		return mapContainer.keySet().hashCode();
	}


	public String toString() {
		StringBuilder builder = new StringBuilder("LinkedHashSet[");
		int available = size();
		for (A a : this) {
			builder.append(a);
			if (available > 1) {builder.append(", ");}
			available--;
		}
		builder.append("]");
		return builder.toString();
	}
}
